#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//
//int main()
//{
//	char c;
//	int v0 = 0, v1 = 0, v2 = 0;
//		do
//		{
//			switch (c = getchar())
//			{
//			case'a':case'A':
//			case'e':case'E':
//			case'i':case'I':
//			case'o':case'O':
//			case'u':case'U':v1 += 1;
//			default:v0 += 1; v2 += 1;
//			}
//		} while (c != '\n');
//		printf("v0=%d,v1=%d,v2=%d\n", v0, v1, v2);
//		return 0;
//}

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;
void QueueInit(Que* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueueDestroy(Que* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueuePush(Que* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->data = x;
	newnode->next = NULL;

	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

	pq->size++;
}

void QueuePop(Que* pq)
{
	assert(pq);
	//assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}

	pq->size--;
}

QDataType QueueFront(Que* pq)
{
	assert(pq);
	//assert(!QueueEmpty(pq));

	return pq->head->data;
}

QDataType QueueBack(Que* pq)
{
	assert(pq);
	//assert(!QueueEmpty(pq));

	return pq->tail->data;
}

bool QueueEmpty(Que* pq)
{
	assert(pq);

	return pq->head == NULL;
}

int QueueSize(Que* pq)
{
	assert(pq);

	return pq->size;
}





typedef struct {
	Que q1;
	Que q2;
} MyStack;


MyStack* myStackCreate() {
	MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
	QueueInit(&pst->q1);
	QueueInit(&pst->q2);
	return pst;
}

void myStackPush(MyStack* st, int x) {
	if (!QueueEmpty(&st->q1))
	{
		QueuePush(&st->q1, x);
	}
	else
	{
		QueuePush(&st->q2, x);
	}
}

int myStackPop(MyStack* st) {
	Que* empty = &st->q1;
	Que* noempty = &st->q2;
	if (!QueueEmpty(&st->q1))
	{
		noempty = &st->q1;
		empty = &st->q2;
	}
	while (QueueSize(noempty) > 1)
	{
		QueuePush(empty, QueueFront(noempty));
		QueuePop(noempty);
	}
	int top = QueueFront(noempty);
	QueuePop(noempty);
	return top;
}

int myStackTop(MyStack* st) {
	if (!QueueEmpty(&st->q1))
	{
		return QueueBack(&st->q1);
	}
	else
	{
		return QueueBack(&st->q2);
	}
}

bool myStackEmpty(MyStack* st) {
	return QueueEmpty(&st->q1) && QueueEmpty(&st->q2);

}

void myStackFree(MyStack* st) {
	QueueDestroy(&st->q1);
	QueueDestroy(&st->q2);
	free(st);
}
